#!/usr/bin/python2.4
# -*- coding: utf-8 -*-
#
#    Pydapt - Adaptive Devices Framework for Python
#    Copyright (C) 2009  Rodolpho Eckhardt <rodolpho@eckhardt.com.br>
#
#    This program is free software: you can redistribute it and/or modify
#    it under the terms of the GNU General Public License as published by
#    the Free Software Foundation, either version 3 of the License, or
#    (at your option) any later version.
#
#    This program is distributed in the hope that it will be useful,
#    but WITHOUT ANY WARRANTY; without even the implied warranty of
#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
#    GNU General Public License for more details.
#
#    You should have received a copy of the GNU General Public License
#    along with this program.  If not, see <http://www.gnu.org/licenses/>.
#
#    You can contact the Pydapt team at pydapt@googlegroups.com
#
"""Base interfaces for framework.

TODO(rodolpho): review module classes docstring.
"""

__author__ = "rodolpho@eckhardt.com.br (Rodolpho Eckhardt)"


import copy
import datetime
import md5
import random


class IdGenerator(object):
  """Generator of unique ID strings."""

  def __init__(self):
    self.__id_database = []

  def CreateNewId(self):
    """Creates a new ID.

    Returns:
      A string containing an unique ID.
    """
    new_id = md5.md5(
        datetime.datetime.now().ctime() + str(random.random())).hexdigest()
    while new_id in self.__id_database:
      new_id = md5.md5(
          datetime.datetime.now().ctime() + str(random.random())).hexdigest()
    self.__id_database.append(new_id)
    return new_id


# ID generator for the whole module.
__id_generator = IdGenerator()


class Error(Exception):
  """Module level exception."""
  pass


class ConfigurationInUseException(Error):
  """Exception raised when the user tries to remove a configuration in use."""
  pass


class InvalidConfiguration(Error):
  """Exception raised when an invalid configuration is referenced."""
  pass


class InvalidInputSymbol(Error):
  """Exception raised when an invalid symbol is read by the device."""
  pass


class InvalidOutputSymbol(Error):
  """Exception raised when an invalid symbol is written by a device."""
  pass


class NonDeterminism(Error):
  """Exception raised when a non-determinism is reached."""
  pass


class Device(object):
  """Class which represents a rule-driven device.

  Attributes:
    TODO(rodolpho): review object attributes.
  """

  def __init__(self, input_alphabet, output_alphabet, name=None):
    """Initializes the device with the given arguments."""
    self.__id = __id_generator.CreateNewId()
    self.input_alphabet = input_alphabet
    self.output_alphabet = output_alphabet
    if name:
      self.name = name
    else:
      self.name = ''
    self.__current_configuration = None
    self.__initial_configuraiton = None
    self.__acceptance_configurations = []
    # Configurations are indexed by ID
    self.__configurations = {}
    # Rules are indexed by (current_configuration, input_symbol)
    self.__rule_sets = {}

  def __unicode__(self):
    return self.name

  def __str__(self):
    return self.name

  def AddAcceptanceConfiguration(self, configuration):
    """Sets the given configuration as an acceptance one.

    Args:
      configuration: the configuration belonging to this device which will
          become an acceptance one.
    """
    if configuration not in self.__configurations.values():
      raise InvalidConfiguration(
          ('The given configuration does not belong to '
           'this device: %s') % configuration.name)
    if configuration not in self.__acceptance_configurations:
      self.__acceptance_configurations.append(configuration)

  def AddConfiguration(self, name=None, is_acceptance=False):
    """Creates a new configuration for this device.

    Args:
      name: an optional string containing the name of the new configuration.
      is_acceptance: a boolean indicating if the new configuration is an
          acceptance one.

    Returns:
      The new Configuration object belonging to this device.
    """
    c = Configuration(name)
    self.__configurations[c.id] = c
    if is_acceptance:
      self.__acceptance_configurations.append(c)
    return c

  def Copy(self):
    """Copies this device.

    Returns:
      A deep copy of this device - also a Device object.
    """
    reference_table = {}
    for rule_set in self.__rule_sets.values():
      for r in rule_set:
        if (getattr(r, 'adaptive_pre_function', None) or
            getattr(r, 'adaptive_post_function', None)):
          reference_table[r.id] = (getattr(r, 'adaptive_pre_function', None),
                                   getattr(r, 'adaptive_post_function', None))
          r.adaptive_pre_function = None
          r.adaptive_post_function = None
    copied_device = copy.deepcopy(self)
    for rule_id in reference_table.keys():
      # Re-establish functions in current device!
      r = self.FindRuleById(rule_id)
      r.adaptive_pre_function = reference_table[r.id][0]
      r.adaptive_post_function = reference_table[r.id][1]
      # Re-establish functions in copied device
      r = copied_device.FindRuleById(rule_id)
      r.adaptive_pre_function = reference_table[r.id][0]
      r.adaptive_post_function = reference_table[r.id][1]
    return copied_device

  def FindConfigurationById(self, id):
    """Finds the configuration with the given ID.

    Args:
      id: a string containing the ID of the configuration to be found.

    Returns:
      A Configuration object with the given ID if it's found. None if no
      configuration has the given ID. None if no such configuration exists.
    """
    if id in self.__configurations:
      return self.__configurations[id]

  def FindConfigurationByName(self, name):
    """Finds the configurations of this device with the given name.

    Args:
      name: a string containing the desired name of the configuration.

    Returns:
      A list of all configurations with the given name.
    """
    return [c for c in self.__configurations.values() if (c.name == name)]

  def FindRuleById(self, id):
    """Finds the rule with the given ID.

    Args:
      id: a string containing the ID of the rule to be found.

    Returns:
      A Rule object with the given ID if it's found. None if no rule has the
      given ID. None if such rule does not exist.
    """
    for rule_set in self.__rule_sets.values():
      for rule in rule_set:
        if rule.GetId() == id:
          return rule

  def FindRuleByName(self, name):
    """Finds the rules of this device with the given name.

    Args:
      name: a string containing the desired rule name.

    Returns:
      A list of all rules with the given name.
    """
    rules = []
    for rule_set in self.__rule_sets.values():
      for rule in rule_set:
        if rule.name == name:
          rules.append(rule)
    return rules

  def FindRules(self, input_symbol):
    """Finds all applicable rules given the current state and input.

    Args:
      input_symbol: a string containing one input symbol.

    Returns:
      A list containing all Rule objects which current_configuration attribute
      is the same as the current_configuration of the device and the
      input_symbol attribute is the same as the input_symbol argument.
    """
    keys = ((self.__current_configuration, input_symbol),
            (self.__current_configuration, None),)
    rules = []
    for key in keys:
      if key in self.__rule_sets:
        rules.extend(self.__rule_sets[key])
    return rules

  def GetAcceptanceConfigurations(self):
    """Returns the acceptance configuratins of this device.

    Returns:
      A list containing Configuration objects which represents acceptance
      configurations of this device.
    """
    return self.__acceptance_configurations

  def GetCurrentConfiguration(self):
    """Returns the current configuration of this device.

    Returns:
      The Configuration object which represents the current configuration of the
      device.
    """
    return self.__current_configuration

  def GetId(self):
    """Returns this instance ID.

    Returns:
      A string containing the ID of this instance - an unique identifier.
    """
    return self.__id

  def GetInitialConfiguration(self):
    """Returns the initial configuration of this device.

    Returns:
      The Configuration object which represents the device initial
      configuration.
    """
    return self.__initial_configuraiton

  def GetRules(self):
    """Returns all the device rules.

    Returns:
      A list containing all the rules belonging to this device.
    """
    rules = []
    for rule_set in self.__rule_sets.values():
      for rule in rule_set:
        rules.append(rules)
    return rules

  def IsAccepting(self):
    """Checks if the current configuration of the device is an accepting one.

    Returns:
      True if the attribute current_configuration belongs to the list in
        attribute acceptance_configurations.
    """
    return self.__current_configuration in self.__acceptance_configurations

  def RemoveAcceptanceConfiguration(self, configuration):
    """Set the given configuration as a non-acceptance one.

    Args:
      configuration: a Configuration object which will be removed from the
          acceptance configuration set.

    Raises:
      InvalidConfiguration: if the given configuration does not belong to this
          device.
    """
    if ((configuration not in self.__configurations.values()) or
        (configuration not in self.__acceptance_configurations)):
      raise InvalidConfiguration(
          ('The given configuration does not belong to this device or '
           'is not an acceptance one: %s') % configuration.name)
    self.__acceptance_configurations.remove(configuration)

  def RemoveConfiguration(self, configuration):
    """Completely removes the given configuration from this device.

    Args:
      configuration: the Configuration object to be removed from the device.

    Raises:
      InvalidConfiguration: if the given configuration does not belong to this
          device.
      ConfigurationInUseException: if the given configuration is used by any
          rule.
    """
    if configuration not in self.__configurations.values():
      raise InvalidConfiguration(
          ('This configuration does not belong to this '
           'device: %s') % configuration.name)
    for r in self.GetRules():
      if ((r.current_configuration == configuration) or
          (r.next_configuration == configuration)):
        raise ConfigurationInUseException(
          ('This configuration (%s) is used by a rule: '
           '%s') % (configuration.name, r.name))
    if configuration in self.__acceptance_configurations:
      self.__acceptance_configurations.remove(configuration)
    self.__configurations.pop(configuration.id)

  def Reset(self):
    """Resets the device to its initial configuration."""
    self.__current_configuration = self.__initial_configuration

  def SetInitialConfiguration(self, configuration):
    """Sets the initial configuration of this device.

    Args:
      configuration: a Configuration object belonging to this device, which is
          going to be its first configuration.

    Raises:
      InvalidConfiguration: if the given configuration does not belong to this
          device.
    """
    if configuration not in self.__configurations.values():
      raise InvalidConfiguration(
          ('This configuration does not belong to this '
           'device: %s') % configuration.name)
    self.__initial_configuration = configuration


class DeviceRunner(object):
  """Class which runs a Device."""

  def Consume(self, device, input_symbol):
    """Consumes the given input symbol through the device.

    Because this runner is non-deterministic, this method will return a list
    of all new configurations and their respective output symbol.

    Args:
      input_symbol: a string containing any input symbol belonging to the
        input_alphabet attribute.

    Returns:
      A list of tuples, for each possible new configuration. The first item of
        the tuple is a copy of the device, but in its new configuration. The
        second item is the output symbol, if any, written by the device during
        the rule execution. The third item is the rule used to consume the
        input.

    Raises:
      InvalidInputSymbol: raised when the input_symbol argument does not belong
        to the input_alphabet attribute.
    """
    if input_symbol not in device.input_alphabet:
      raise InvalidInputSymbol()
    results = []
    for rule in device.FindRules(input_symbol):
      new_device = device.Copy()
      new_device.current_configuration = new_device.FindConfigurationById(
          rule.next_configuration.id)
      if rule.output_symbol not in new_device.output_alphabet:
        raise InvalidOutputSymbol()
      results.append((new_device, rule.output_symbol, rule))
    return results

  def Run(self, device, input_string):
    """Runs the given device with the input string.

    Args:
      device: a Device object which will be executed.
      input_string: a string containing the sequence of input symbols to be
        parsed.

    Returns:
      A tuple in which the first item is a boolean indicating if the device
        accepted or not the given input sequence of symbols. The second item is
        a list of all strings written by the device during the execution, if it
        accepted the input string - if not, this will be an empty list. The
        third item is a list of all automata in their final acceptance states.
    """
    to_be_executed = {}
    if input_string:
      to_be_executed[(device.current_configuration, input_string)] = (device,
                                                                      '', [])
    executed = {}
    while len(to_be_executed) > 0:
      executing = to_be_executed.keys()[0]
      device, output_string, rule_list = to_be_executed[executing]
      input_string = executing[1]
      results = self.Consume(device, input_string[0])
      for result in results:
        next_device, output_symbol, rule = result
        if rule.input_symbol == input_string[0]:
          next_input_string = input_string[1:]
        else:
          next_input_string = input_string
        new_rule_list = copy.copy(rule_list)
        new_rule_list.append(rule.id)
        t = (next_device.current_configuration, next_input_string)
        if next_input_string or next_device.FindRules(''):
          # There is still input to be parsed or an empty transition still.
          to_be_executed[t] = (next_device, output_string + output_symbol,
                               new_rule_list)
        else:
          executed[t] = (next_device, output_string + output_symbol,
                         new_rule_list)
      executed[executing] = to_be_executed[executing]
      to_be_executed.pop(executing)
    outputs = []
    devices = []
    for execution in executed.keys():
      if execution[1]:
        # There was still string to be parsed
        continue
      device, output_string, rule_list = executed[execution]
      if device.IsAccepting():
        outputs.append(output_string)
        devices.append(device)
    if outputs:
      return True, outputs, devices
    return False, outputs, devices


class DeterministicDeviceRunner(DeviceRunner):
  """Class which runs a deterministic Device."""

  def Consume(self, device, input_symbol):
    """Consumes the given input symbol through the device.

    Because this runner is non-deterministic, this method will return a list
    of all new configurations and their respective output symbol.

    Args:
      input_symbol: a string containing any input symbol belonging to the
        input_alphabet attribute.

    Returns:
      A list of tuples, for each possible new configuration. The first item of
        the tuple is a copy of the device, but in its new configuration. The
        second item is the output symbol, if any, written by the device during
        the rule execution. The third item is the rule used to consume the
        input.

    Raises:
      InvalidInputSymbol: raised when the input_symbol argument does not belong
        to the input_alphabet attribute.
    """
    if input_symbol not in device.input_alphabet:
      raise InvalidInputSymbol()
    rules = device.FindRules(input_symbol)
    if len(rules) > 1:
      raise NonDeterminism()
    if rules:
      new_device = device.Copy()
      new_device.current_configuration = new_device.FindConfigurationById(
          rules[0].next_configuration.id)
      if rules[0].output_symbol not in new_device.output_alphabet:
        raise InvalidOutputSymbol()
      return ((new_device, rules[0].output_symbol, rules[0]),)
    return tuple()


class AdaptiveDeviceRunner(DeviceRunner):
  """Class which runs a Device."""

  def Consume(self, device, input_symbol):
    """Consumes the given input symbol through the device.

    Because this runner is non-deterministic, this method will return a list
    of all new configurations and their respective output symbol.

    Args:
      input_symbol: a string containing any input symbol belonging to the
        input_alphabet attribute.

    Returns:
      A list of tuples, for each possible new configuration. The first item of
        the tuple is a copy of the device, but in its new configuration. The
        second item is the output symbol, if any, written by the device during
        the rule execution. The third item is the rule used to consume the
        input. The fourth item is a boolean indicating if the rule was removed
        by an adaptive pre function.

    Raises:
      InvalidInputSymbol: raised when the input_symbol argument does not belong
        to the input_alphabet attribute.
    """
    if input_symbol not in device.input_alphabet:
      raise InvalidInputSymbol()
    results = []
    for rule in device.FindRules(input_symbol):
      new_device = device.Copy()
      new_device.name = new_device.name + '_copy'
      eq_rule = new_device.FindRuleById(rule.id)
      if getattr(eq_rule, 'adaptive_pre_function', None):
        eq_rule.adaptive_pre_function(new_device, eq_rule)
      eq_rule = new_device.FindRuleById(rule.id)
      if not eq_rule:
        # This rule was removed!!
        # We won't change configuration, nor output.
        results.append((new_device, '', rule, True))
      else:
        # This rule is still here
        new_device.current_configuration = new_device.FindConfigurationById(
            eq_rule.next_configuration.id)
        if eq_rule.output_symbol not in new_device.output_alphabet:
          raise InvalidOutputSymbol()
        if getattr(eq_rule, 'adaptive_post_function', None):
          eq_rule.adaptive_post_function(new_device, eq_rule)
        results.append((new_device, eq_rule.output_symbol, eq_rule, False))
    return results

  def Run(self, device, input_string):
    """Runs the given adaptive device with the input string.

    Args:
      device: a Device object which will be executed.
      input_string: a string containing the sequence of input symbols to be
        parsed.

    Returns:
      A tuple in which the first item is a boolean indicating if the device
        accepted or not the given input sequence of symbols. The second item is
        a list of all strings written by the device during the execution, if it
        accepted the input string - if not, this will be an empty list. The
        third item is a list of all automata in their final acceptance states.
    """
    to_be_executed = {}
    if input_string:
      to_be_executed[(device.current_configuration, input_string)] = (device,
                                                                      '', [])
    executed = {}
    while len(to_be_executed) > 0:
      executing = to_be_executed.keys()[0]
      device, output_string, rule_list = to_be_executed[executing]
      input_string = executing[1]
      results = self.Consume(device, input_string[0])
      for result in results:
        next_device, output_symbol, rule, removed_on_pre = result
        # Check if the rule was removed
        if not removed_on_pre and rule.input_symbol == input_string[0]:
          next_input_string = input_string[1:]
        else:
          next_input_string = input_string
        new_rule_list = copy.copy(rule_list)
        new_rule_list.append(rule.id)
        t = (next_device.current_configuration, next_input_string)
        if next_input_string or next_device.FindRules(''):
          # There is still input to be parsed or an empty transition still.
          to_be_executed[t] = (next_device, output_string + output_symbol,
                               new_rule_list)
        else:
          executed[t] = (next_device, output_string + output_symbol,
                         new_rule_list)
      executed[executing] = to_be_executed[executing]
      to_be_executed.pop(executing)
    outputs = []
    devices = []
    for execution in executed.keys():
      if execution[1]:
        # There was still string to be parsed
        continue
      device, output_string, rule_list = executed[execution]
      if device.IsAccepting():
        outputs.append(output_string)
        devices.append(device)
    if outputs:
      return True, outputs, devices
    return False, outputs, devices


class Configuration(object):
  """Represents a possible configuration for a rule driven device.

  Attributes:
    name: a string containing the name of this configuration.
  """

  def __init__(self, name=None):
    if name:
      self.name = name
    else:
      self.name = ''
    self.id = __id_generator.CreateNewId()

  def __unicode__(self):
    return self.name

  def __str__(self):
    return self.name


class Rule(object):
  """Represents a possible rule for a rule driven device.

  Attributes:
    current_configuration: a Configuration object, which is the initial
      configuration of a device for this rule to be applicable.
    input_symbol: a string containing the symbol which this rule consumes.
    next_configuration: a Configuration object representing the final
      configuration of a device after this rule is executed.
    output_symbol: a string containing the symbol written by the device when
      this rule is executed.
    name: a string containing the name of this rule.
  """

  def __init__(self, current_configuration, input_symbol, next_configuration,
               output_symbol, name=None):
    """Initializes the object with given arguments."""
    self.current_configuration = current_configuration
    self.input_symbol = input_symbol
    self.next_configuration = next_configuration
    self.output_symbol = output_symbol
    if name:
      self.name = name
    else:
      self.name = ''
    self.id = __id_generator.CreateNewId()

  def __unicode__(self):
    return self.name

  def __str__(self):
    return self.name


class AdaptiveRule(Rule):
  """Represents a possible adaptive rule for a rule driven adaptive device.

  Attributes:
    current_configuration: a Configuration object, which is the initial
      configuration of a device for this rule to be applicable.
    input_symbol: a string containing the symbol which this rule consumes.
    next_configuration: a Configuration object representing the final
      configuration of a device after this rule is executed.
    output_symbol: a string containing the symbol written by the device when
      this rule is executed.
    adaptive_pre_function: a callable which gets called before this rule is
      executed.
    adaptive_post_function: a callable which gets called after this rule is
      executed.
    name: a string containing the name of this rule.
  """

  def __init__(self, current_configuration, input_symbol, next_configuration,
               output_symbol, adaptive_pre_function=None,
               adaptive_post_function=None, name=None):
    """Initializes the object with given arguments."""
    super(AdaptiveRule, self).__init__(current_configuration, input_symbol,
                                       next_configuration, output_symbol, name)
    self.adaptive_pre_function = adaptive_pre_function
    self.adaptive_post_function = adaptive_post_function